package com.gitee.ywj1352.kaishi.Str;

import java.util.ArrayList;
import java.util.List;

/**
 * @author wenjie.yang
 * @date 4/28/2020 2:25 PM
 */
public class 复原ip {

    public static void main(String[] args) {
        List<String> list = restoreIpAddresses("0000");

        list.forEach(s -> System.out.println(s));

    }

    public static List<String> restoreIpAddresses(String s) {
        List<String> ans = new ArrayList<>();
        dfs(s, 0, new ArrayList<String>(), ans);
        return ans;
    }


    public static void dfs(String s, int startIdx, List<String> cur, List<String> ans) {
        if (cur.size() == 4) {
            if (startIdx != s.length()) {
                return;
            }
            String join = String.join(".", cur);
            if (!ans.contains(join)) {
                ans.add(join);
            }
            return;
        }
        for (int i = 0; i < 4; i++) {
            if (startIdx + i > s.length()) {
                break;
            }
            String str = i + startIdx + 1 > s.length() ? s.substring(startIdx) : s.substring(startIdx, i + startIdx + 1);
            if ((str.startsWith("0") && str.length() > 1) || startIdx + 1 > s.length() || (Integer.valueOf(str) > 255)) {
                continue;
            }

            cur.add(str);
            dfs(s, i + startIdx + 1, cur, ans);
            cur.remove(cur.size() - 1);
        }
    }

}
